from typing import List
from collections import Counter

class Solution:
    def leastInterval1(self, tasks: List[str], n: int) -> int:
        tmp1 = {}
        for t in tasks:
            if t in tmp1:
                tmp1[t] += 1
            else:
                tmp1[t] = 1
        tasks = sorted(tmp1.items(), key=lambda x: x[1])

        ret = 0
        tmp2 = []
        while tasks:
            i = 0
            while i < n + 1 and tasks:
                t = tasks.pop()
                t_n = t[1] - 1
                if t_n:
                    tmp2.append((t[0], t_n))
                i += 1
            tmp3 = []
            while tmp2 or tmp3:
                if tmp2 and (not tmp3 or tmp2[-1][1] < tmp3[-1][1]):
                    t = tmp2.pop()
                else:
                    t = tmp3.pop()
                while tasks and t[1] < tasks[-1][1]:
                    tmp3.append(tasks.pop())
                tasks.append(t)
            ret += n + 1 if tasks else i
        return ret

    def leastInterval2(self, tasks: List[str], n: int) -> int:
        tasks = sorted(Counter(tasks).values())

        ret = 0
        while tasks:
            lth = min(len(tasks), n + 1)
            tmp = []
            for _ in range(lth):
                r = tasks.pop() - 1
                if r:
                    tmp.append(r)
            tmp2 = []
            while tmp or tmp2:
                if tmp and (not tmp2 or tmp[-1] < tmp2[-1]):
                    t = tmp.pop()
                else:
                    t = tmp2.pop()
                while tasks and tasks[-1] > t:
                    tmp2.append(tasks.pop())
                tasks.append(t)

            ret += n + 1 if tasks else lth
        return ret

    def leastInterval(self, tasks: List[str], n: int) -> int:
        rest = Counter(tasks).values()

        max_task = max(rest)
        max_task_n = Counter(rest)[max_task]
        
        return max((max_task - 1) * (n + 1) + max_task_n, len(tasks))
        
if __name__ == "__main__":
    s = Solution()

    tasks = ["A", "A", "A", "B", "B", "B"]
    n = 2
    resp = s.leastInterval(tasks, n)
    print(resp, 8)

    tasks = ["A", "A", "A", "B", "B", "B"]
    n = 0
    resp = s.leastInterval(tasks, n)
    print(resp, 6)

    tasks = ["A", "A", "A", "A", "A", "A", "B", "C", "D", "E", "F", "G"]
    n = 2
    resp = s.leastInterval(tasks, n)
    print(resp, 16)

    tasks = ["A", "A", "A", "B", "B", "B", "C", "C", "C", "D", "D", "E"]
    n = 2
    resp = s.leastInterval(tasks, n)
    print(resp, 12)
